class MedianFinder {
public:
    priority_queue<int> left;//最大堆
    priority_queue<int,vector<int>,greater<int>> right;//最小堆
    MedianFinder() {
    }
    
    void addNum(int num) 
    {
        if (left.size() == right.size()) {
            right.push(num);//如果两个stl中元素的数量相等，先往right中放值，然后将right中最小的值放入到left中
            left.push(right.top());
            right.pop();//再将这个值从right中拿取
        } else 
        {
            left.push(num);//两者的值不等
            right.push(left.top());//将left中最大的值放入到right中
            left.pop();
        }
    }
    double findMedian() {
        if(left.size()>right.size())
        {
            //说明此时的中位数就是left的最大值+right的最小值/2
            return left.top();
        }   
        else
        {
            return (left.top()+right.top())/2.0;
        }
    } 
};
